/*
Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.
*/

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        Sudoku_solver(0, board);
    }
private:
    bool Sudoku_solver(int cur, vector<vector<char> > &board) {
        for (int i = cur; cur < 81; cur++) {
            if (board[cur/9][cur%9] == '.') break;
        }
        if (cur == 81) return true; // all board filled
        // try to fill in this point
        int x = cur/9, y = cur % 9;
        for (int num = 1; num < 10; num++) {
            board[x][y] = '0' + num;
            if (ValidSukudo(cur, board) && Sudoku_solver(cur, board)) {
                // found one solution
                return true;
            }
        }
        board[x][y] = '.'; // reset to previous value
        return false;
    }
    bool ValidSukudo(int cur, vector<vector<char> > &board) {
        int row = cur/9, col = cur%9;
        char c = board[row][col];
        for (int j = 0; j < board[0].size(); j++) {
            if (j != col && board[row][j] == c) return false;
        }
        for (int i = 0; i < board.size(); i++) {
            if (i != row && board[i][col] == c) return false;
        }
        int mulx = row / 3, muly = col / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int x = mulx*3+i, y = muly*3+j;
                if (x == row && y == col) continue;
                if (board[x][y] == c) return false;
            }
        }
        return true;
    }
};
